package leetcode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
// 方法一：递归
// 1. 以preorder的第一个元素或postorder的最后一个元素为根节点的值
// 2. 以preorder的第二个元素作为左子树的根节点，在postorder中找到该元素的索引i，然后基于索引i可以计算出左右子树的长度
// 3. 最后基于左右子树的长度，分别划分出前序和后序遍历序列中的左右子树，递归构造左右子树即可
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
	postMap := make(map[int]int)
	for index, v := range postorder {
		postMap[v] = index
	}
	var dfs func(prel, prer, postl, postr int) *TreeNode
	dfs = func(prel, prer, postl, postr int) *TreeNode {
		if prel > prer {
			return nil
		}
		root := &TreeNode{Val: preorder[prel]}
		if prel == prer {
			return root
		}
		leftRootIndex := postMap[preorder[prel+1]]
		leftLength := leftRootIndex - postl + 1
		root.Left = dfs(prel+1, prel+leftLength, postl, leftRootIndex)
		root.Right = dfs(prel+leftLength+1, prer, leftRootIndex+1, postr-1)
		return root
	}
	return dfs(0, len(preorder)-1, 0, len(postorder)-1)
}
